package LeetCode75;

import publicClass.TreeNode;

import java.util.ArrayList;

/**
 * 1161. 最大层内元素和
 * 给你一个二叉树的根节点 root。设根节点位于二叉树的第 1 层，而根节点的子节点位于第 2 层，依此类推。
 *
 * 请返回层内元素之和 最大 的那几层（可能只有一层）的层号，并返回其中 最小 的那个。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：root = [1,7,0,7,-8,null,null]
 * 输出：2
 * 解释：
 * 第 1 层各元素之和为 1，
 * 第 2 层各元素之和为 7 + 0 = 7，
 * 第 3 层各元素之和为 7 + -8 = -1，
 * 所以我们返回第 2 层的层号，它的层内元素之和最大。
 * 示例 2：
 *
 * 输入：root = [989,null,10250,98693,-89388,null,null,null,-32127]
 * 输出：2
 *
 *
 * 提示：
 *
 * 树中的节点数在 [1, 104]范围内
 * -105 <= Node.val <= 105
 */
public class T1161_最大层内元素和 {

    //第一个数是最大值 第二数是层数
  int[] result = new int[2];

    public int maxLevelSum(TreeNode root) {

        result[0] = Integer.MIN_VALUE;
        bfs(root);

        return result[1];

    }

    void bfs(TreeNode root){

        ArrayList<TreeNode> currList = new ArrayList<>();
        currList.add(root);

        int count = 1; //记录层数
        while (!currList.isEmpty()) {
            ArrayList<TreeNode> nextLine = new ArrayList<>();
            int sum = 0; //记录本层的 和
            for (TreeNode treeNode : currList) {
                sum += treeNode.val;
                if (treeNode.left!=null){
                    nextLine.add(treeNode.left);
                }
                if (treeNode.right!=null){
                    nextLine.add(treeNode.right);
                }
            }
            if (sum >result[0]){
                result[0] = sum;
                result[1] = count;
            }
            currList = nextLine;
            count++;
        }

    }

}
